package com.LeeCode;

/**
 * 基于陈述统计最多好人数
 */

public class Code2151 {
    public static void main(String[] args) {
        int[][] statements = {
                {2, 0},
                {0, 2}
        };
        System.out.println(new Code2151().maximumGood(statements));
    }

    public int maximumGood(int[][] statements) {
        int n = statements.length;
        int maxGood = 0;

        // 枚举所有可能的角色组合（0 ~ 2^n - 1）
        for (int mask = 0; mask < (1 << n); mask++) {
            if (isValid(statements, mask, n)) {
                maxGood = Math.max(maxGood, Integer.bitCount(mask));
            }
        }

        return maxGood;
    }

    // 验证当前 mask 是否合法（所有好人说的话必须都正确）
    private boolean isValid(int[][] statements, int mask, int n) {
        for (int i = 0; i < n; i++) {
            // 如果 i 是好人（mask 中第 i 位是 1）
            if ((mask & (1 << i)) != 0) {
                for (int j = 0; j < n; j++) {
                    if (statements[i][j] == 2) continue;

                    // i 说 j 是好人（statements[i][j] == 1），但 mask 中 j 不是好人
                    // 或者 i 说 j 是坏人（statements[i][j] == 0），但 mask 中 j 是好人
                    boolean isGood = (mask & (1 << j)) != 0;
                    if (statements[i][j] == 1 && !isGood) return false;
                    if (statements[i][j] == 0 && isGood) return false;
                }
            }
        }
        return true;
    }
}
